package chapter03;

import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * 问题1：使用迭代器的原因？
 * 在程序开发中，经常需要遍历集合中的所有元素。数组中我们可以使用for循环通过其索引来遍历整个集合，
 * 但是有些集合中没有索引，我们无法通过for循环来遍历，针对这种需求，JDK专门提供了一个接口java.util.Iterator
 *
 * 问题2： 在使用迭代器遍历集合时,为何不能使用集合的remove方法?
 * 参见：https://blog.csdn.net/xiaofengcanyuelong/article/details/79007686
 *
 * @param <E>
 */
public class MyLinkedList<E> implements Iterable<E> {
    private int size = 0;

    /**
     * 修改次数
     */
    private int modCount = 0;

    private Node<E> begin;

    private Node<E> end;

    public MyLinkedList() {
        doClear();
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size() == 0;
    }

    public void clear() {
        doClear();
    }

    /**
     * Change the size of this collection to zero.
     */
    public void doClear() {
        begin = new Node<E>(null, null, null);
        end = new Node<E>(null, begin, null);
        begin.next = end;

        size = 0;
        modCount++;
    }

    public boolean contains(E e) {
        Node<E> p  = begin.next;
        while (p != end && !p.data.equals(e)) {
            p = p.next;
        }
        return p != end;
    }

    public boolean add(E e) {
        add(size(), e);
        return true;
    }

    public boolean addFrist(E e) {
        add(0, e);
        return true;
    }

    public boolean addLast(E e) {
        add(size() - 1, e);
        return false;
    }

    public boolean remove(int index) {
        return false;
    }

    public void add(int index, E e) {
        addBefore(getNode(index), e);
    }

    private void addBefore(Node<E> p, E e) {
        Node<E> newNode = new Node<E>(e, p.prev, p);
        newNode.prev.next = newNode;//p.prev.next = newNode;都可以
        p.prev = newNode;
        size++;
        modCount++;
    }

    private Node<E> getNode(int index) {
        Node<E> current;
        if (index < 0 || index > size()) {
            throw new IndexOutOfBoundsException();
        }
        if (index < size() / 2) {
            // begin -> end
            current = begin.next;
            for (int i = 0; i < index; i++) {
                current = current.next;
            }
        }else {
            // end -> begin
            current = end;
            for (int i = size(); i > index; i--) {
                current = current.prev;
            }
        }
        return current;
    }

    public E remove() {
        return null;
    }

    public boolean remove(E e) {
        return false;
    }

    public boolean removeFirst(E e) {
        return false;
    }

    public boolean removeLast(E e) {
        return false;
    }

    public E getFirst() {
        return null;
    }

    public E getLast() {
        return null;
    }

    public E remove(Node<E> p) {
        p.prev.next = p.next;
        p.next.prev = p.prev;
        size--;
        modCount--;
        return p.data;
    }

    public Node<E> getNode(int index, int lower, int upper) {
        Node<E> p;
        if (index < lower || index > upper) {
            throw new IndexOutOfBoundsException();
        }
        if (index < size / 2) {
            // begin -> end
            p = begin.next;
            for (int i = 0; i < index; i++) {
                p = p.next;
            }
        }else {
            // end -> begin
            p = end.prev;
            for (int i = size() - 1; i > index; i--) {
                p = p.prev;
            }
        }
        return p;
    }

    public Iterator<E> iterator() {
        return new LinkedListIterator();
    }

    /**
     * This run in O(MN), where M is the size of the items, and N is the size of the list.
     * @param items
     */
    public void removeAll(Iterable<? extends E> items) {
        Iterator<? extends E> iteratorItems = items.iterator();
        E item, element;
        while (iteratorItems.hasNext()) {
            item = iteratorItems.next();
            Iterator<E> iteratorList = iterator();
            while (iteratorList.hasNext()) {
                element = iteratorList.next();
                if (element.equals(item)) {
                    iteratorList.remove();
                }
            }
        }
    }

    private class LinkedListIterator implements Iterator<E> {
        //游标,指向下一个要返回的元素
        private Node<E> current = begin;
        //修改次数--->用于检测在迭代期间被修改的情况,expectedModeCount初始值是modCount,通过expectedModeCount与modCount的比较来进行错误检测
        private int expectedModCount = modCount;
        private boolean okToRemove = false;

        public boolean hasNext() {
            return current != end;
        }

        public E next() {
            if (modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            E nextItem = current.data;
            current = current.next;
            okToRemove = true;

            return nextItem;
        }

        public void remove() {
            if (modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }
            if (!okToRemove) {
                throw new IllegalStateException();
            }
            MyLinkedList.this.remove(current.prev);
            expectedModCount++;
            okToRemove = false;
        }
    }


    private static class Node<E> {
        public E data;
        private Node<E> prev;
        private Node<E> next;

        public Node() {
        }

        public Node(E data, Node<E> prev, Node<E> next) {
            this.data = data;
            this.prev = prev;
            this.next = next;
        }
    }

}
